Fenwick Tree

Posted: 2026-03-27 Tags: cs algorithm

contents

펜윅 트리(Fenwick Tree), 또는 이진 인덱스 트리(Binary Indexed Tree, BIT) 라고도 널리 알려진 자료구조에 대해 알아보겠습니다.

이 트리는 매우 우아하고 메모리 효율적이며, 동적 누적 합(Dynamic Prefix Sums) 이라는 단 하나의 특정 문제를 완벽하게 해결하기 위해 고안되었습니다.

1. 해결하려는 문제

$N$개의 숫자로 이루어진 배열이 있다고 상상해 보세요. 다음 두 가지 연산을 반복적으로 수행해야 합니다:

업데이트 (Update): 특정 인덱스의 값을 변경하거나 더합니다.
쿼리 (Query): 인덱스 $1$부터 $i$까지의 모든 요소의 합(누적 합)을 구합니다.

기존의 일반적인 방법들이 이 두 연산의 균형을 맞추는 데 어떻게 실패하는지 살펴봅시다.

접근 방식	업데이트 시간	누적 합 쿼리 시간	설명
일반 배열 (Standard Array)	$O(1)$	$O(N)$	값 변경은 즉시 가능하지만, 합을 구하려면 배열을 루프 돌아야 합니다.
누적 합 배열 (Prefix Sum Array)	$O(N)$	$O(1)$	합은 즉시 알 수 있지만, 값 하나를 바꾸면 그 뒤의 모든 누적 합을 다시 계산해야 합니다.
펜윅 트리 (BIT)	$O(\log N)$	$O(\log N)$	비트 연산을 활용하여 완벽한 로그 시간(Logarithmic) 균형을 맞춥니다.

2. 핵심 직관: 2의 거듭제곱

펜윅 트리는 근본적인 수학적 사실에 기반합니다: 모든 정수는 2의 거듭제곱들의 합으로 표현할 수 있다 (이것이 바로 이진법의 원리입니다).

예를 들어, 숫자 $13$은 이진수로 1101입니다.

$13 = 8 + 4 + 1$

인덱스 $1$부터 $13$까지의 누적 합을 구하고 싶을 때, 펜윅 트리는 13개의 숫자를 일일이 더하지 않습니다. 대신 범위를 정확히 $3$개의 미리 계산된 덩어리(Chunk)로 나눕니다:

길이가 $8$인 덩어리 ($1 \dots 8$ 커버)
길이가 $4$인 덩어리 ($9 \dots 12$ 커버)
길이가 $1$인 덩어리 ($13 \dots 13$ 커버)

이렇게 하면, 어떤 수 $N$에 대한 쿼리든 최대 $O(\log N)$ 번의 덧셈만으로 해결할 수 있습니다.

3. 마법의 공식: 최하위 비트 (LSB) 추출

트리를 이리저리 건너뛰기 위해서는 인덱스의 가장 마지막에 켜진 비트(Last Set Bit, LSB) 를 추출해야 합니다. LSB는 숫자의 이진수 표현에서 가장 오른쪽에 있는 1을 의미합니다.

$10$ (이진수로 1010)의 경우, LSB는 0010 (즉, $2$)입니다.
$12$ (이진수로 1100)의 경우, LSB는 0100 (즉, $4$)입니다.

비트 연산 트릭:

대부분의 프로그래밍 언어에서 음수는 '2의 보수(Two's Complement)'로 표현됩니다(모든 비트를 반전시킨 후 1을 더함). 이러한 수학적 특성 덕분에, 다음과 같은 마법 같은 $O(1)$ 연산으로 LSB를 분리해낼 수 있습니다:

$$LSB(i) = i \ & \ (-i)$$

4. 배열은 실제로 무엇을 저장하는가?

펜윅 트리는 단순한 1차원 배열로 구현되며, 일반적으로 1-based index (1부터 시작하는 인덱스) 를 사용합니다.

tree[i]를 인덱스 $i$에 저장된 값이라고 합시다.

tree[i]는 특정 구간에 속한 요소들의 합을 저장합니다. 이 구간의 길이는 정확히 $LSB(i)$와 같습니다.

구체적으로, tree[i]는 원본 배열의 다음 범위의 합을 저장합니다:

$$[i - LSB(i) + 1, \quad i]$$

tree[1] ($LSB = 1$): 구간 $[1, 1]$ 저장.
tree[2] ($LSB = 2$): 구간 $[1, 2]$ 저장.
tree[4] ($LSB = 4$): 구간 $[1, 4]$ 저장.
tree[6] ($LSB = 2$): 구간 $[5, 6]$ 저장.

5. 두 가지 주요 연산

A. 쿼리 (인덱스 $i$까지의 누적 합)

$1$부터 $i$까지의 합을 구하려면, tree[i]의 값을 더한 뒤 $i$에서 LSB를 뺍니다. 이 과정을 $i$가 $0$이 될 때까지 반복합니다.

예시: Query(13)

$13$은 1101. tree[13]을 더합니다. LSB($1$)를 뺍니다. 다음 인덱스는 $12$.
$12$는 1100. tree[12]를 더합니다. LSB($4$)를 뺍니다. 다음 인덱스는 $8$.
$8$은 1000. tree[8]을 더합니다. LSB($8$)를 뺍니다. 다음 인덱스는 $0$. 끝!

이동 논리: 트리 아래로(왼쪽으로) 이동.

i = i - (i & -i)

B. 업데이트 (인덱스 $i$에 `delta` 더하기)

원본 배열의 $i$번째 값을 변경하면, tree[i]뿐만 아니라 인덱스 $i$를 포함하고 있는 트리의 모든 더 큰 구간들도 업데이트해야 합니다.

현재 구간을 포함하는 다음으로 큰 구간을 찾으려면 $i$에 LSB를 더합니다.

예시: Update(5, delta)

$5$는 0101. tree[5]에 delta를 더합니다. LSB($1$)를 더합니다. 다음 인덱스는 $6$.
$6$은 0110. tree[6]에 delta를 더합니다. LSB($2$)를 더합니다. 다음 인덱스는 $8$.
$8$은 1000. tree[8]에 delta를 더합니다. LSB($8$)를 더합니다. 다음 인덱스는 $16$. (배열 크기를 넘어가면 멈춤).

이동 논리: 트리 위로(오른쪽으로) 이동.

i = i + (i & -i)

6. 구현 코드 (Java)

깔끔하고 표준적인 펜윅 트리 구현체입니다.

매우 중요한 주의사항: 펜윅 트리는 반드시 1부터 시작하는 인덱스(1-indexed) 를 사용해야 합니다. 만약 인덱스 $0$을 전달하면, 0 & -0 = 0이 되어 업데이트 루프인 i += 0이 무한 루프에 빠지게 됩니다!

public class FenwickTree {
    private int[] tree;
    private int n;

    // 특정 크기로 트리 초기화
    public FenwickTree(int size) {
        // 1-based 인덱싱을 사용하므로 size + 1 크기로 할당합니다.
        this.n = size;
        this.tree = new int[n + 1]; 
    }

    // 인덱스 'i'의 요소에 'delta'를 더함 (1-based index)
    public void add(int i, int delta) {
        if (i <= 0) throw new IllegalArgumentException("인덱스는 0보다 커야 합니다.");
        
        // i를 포함하는 모든 큰 구간을 업데이트하기 위해 트리 위로 이동
        while (i <= n) {
            tree[i] += delta;
            i += (i & -i); // LSB 더하기
        }
    }

    // 1부터 i까지의 누적 합 구하기 (1-based index)
    public int query(int i) {
        int sum = 0;
        
        // 미리 계산된 덩어리들을 누적하며 트리 아래로 이동
        while (i > 0) {
            sum += tree[i];
            i -= (i & -i); // LSB 빼기
        }
        return sum;
    }

    // 특정 구간 [left, right]의 합 구하기
    public int rangeQuery(int left, int right) {
        return query(right) - query(left - 1);
    }
}

7. 복잡도 분석

지표	복잡도	설명
시간 (업데이트)	$O(\log N)$	최악의 경우, 켜진 비트의 수(루프 반복 횟수)는 $\log N$에 비례합니다.
시간 (쿼리)	$O(\log N)$	위와 동일합니다. LSB를 최대 $\log N$번 뺍니다.
공간 복잡도	$O(N)$	데이터와 정확히 같은 크기의 배열(1-based 처리를 위한 +1 포함) 1개만 사용합니다. 포인터나 노드 객체가 필요 없습니다.

요약 비교: 펜윅 트리 vs 세그먼트 트리

세그먼트 트리(Segment Tree) 가 있는데 굳이 왜 이걸 쓰는지 궁금하실 수 있습니다.

펜윅 트리: 코드가 극단적으로 짧고(연산당 3~4줄), 정확히 $N$의 메모리만 사용하며, 상수 시간(Constant factor)이 매우 작아 실제 실행 속도가 압도적으로 빠릅니다. 단점은 덧셈/뺄셈처럼 가역적(Invertible)인 연산에 주로 한정된다는 것입니다.
세그먼트 트리: 코드가 길고 $4N$의 메모리를 사용하지만, 훨씬 유연합니다. 최솟값(min()), 최댓값(max()) 같은 비가역적인 연산도 쉽게 처리할 수 있습니다.

구간 업데이트

기본적으로 제공되는 표준 펜윅 트리는 점 업데이트와 구간 쿼리(Point Update and Range Query, PURQ) 만을 처리합니다. 이를 확장하여 구간 업데이트(Range Updates) 를 처리하려면, 트리가 실제로 저장하는 내용물 자체를 바꿔야 합니다.

이 업그레이드에는 두 가지 단계가 있습니다:

RUPQ: 구간 업데이트 + 점 쿼리 (상대적으로 쉬움)
RURQ: 구간 업데이트 + 구간 쿼리 (고급, 두 개의 트리가 필요함)

하나씩 차근차근 살펴보겠습니다.

1단계: 구간 업데이트 + 점 쿼리 (RUPQ)

$[L, R]$ 구간에 있는 모든 요소에 값 $V$를 더하고, 나중에 "$i$번째 인덱스의 실제 값이 무엇인가?"라고 묻고 싶다고 가정해 봅시다.

핵심 트릭: 차이 배열 (Difference Array)

펜윅 트리에 실제 배열의 값을 저장하는 대신, 인접한 두 요소 간의 차이를 저장합니다: $D[i] = A[i] - A[i-1]$.

이 차이 배열에서 인덱스 $i$까지 누적 합(Prefix sum) 을 구하면, 놀랍게도 실제 $A[i]$의 값을 얻을 수 있습니다!

$$A[i] = D[1] + D[2] + \dots + D[i]$$

업데이트 방법:

구간 $[L, R]$ 전체에 $V$를 더하려면, 차이 배열에서는 단 두 지점만 변경하면 됩니다.

인덱스 $L$에 $V$를 더합니다: 이렇게 하면 $A[L]$과 그 이후의 모든 요소가 계산될 때 $V$만큼 증가합니다.
인덱스 $R + 1$에서 $V$를 뺍니다: 구간이 끝난 직후부터는 다시 원래 값으로 돌아오도록 상쇄시키는 역할을 합니다.

코드 로직 (RUPQ):

// 구간 [L, R]에 V를 더하기 위해
public void updateRange(int L, int R, int V) {
    add(L, V);         // L부터 끝까지 V를 더하는 효과
    add(R + 1, -V);    // R+1부터 끝까지 V를 빼서 상쇄하는 효과
}

// 인덱스 i의 실제 값을 구하기 위해
public int queryPoint(int i) {
    return query(i); // 표준 BIT의 누적 합 로직 그대로 사용
}

2단계: 구간 업데이트 + 구간 쿼리 (RURQ)

이것이 최종 형태입니다. 구간 $[L, R]$에 $V$를 더하고, 나중에 특정 구간 $[X, Y]$의 총합을 묻고 싶을 때 사용합니다.

1단계에서 배운 차이 배열 $D$를 사용할 때, 실제 배열 $A$의 첫 번째 요소부터 인덱스 $x$까지의 누적 합은 수학적으로 어떤 모습이 될까요?

$A[1]$부터 $A[x]$까지의 합을 나열해 봅시다:

$$\sum_{i=1}^{x} A[i] = A[1] + A[2] + \dots + A[x]$$

여기에 $A[i]$ 대신 차이 배열 요소들($D[1] + \dots + D[i]$)을 대입해 봅니다:

$$\sum_{i=1}^{x} A[i] = D[1] + (D[1]+D[2]) + (D[1]+D[2]+D[3]) + \dots$$

$D$ 항들을 기준으로 묶어보면, $D[1]$은 $x$번, $D[2]$는 $(x-1)$번, $D[i]$는 $(x - i + 1)$번 나타나는 것을 알 수 있습니다:

$$\sum_{i=1}^{x} A[i] = \sum_{i=1}^{x} D[i] \times (x - i + 1)$$

이 식을 펜윅 트리로 계산하기 쉽게 두 개의 독립적인 시그마(합)로 쪼갤 수 있습니다:

$$\sum_{i=1}^{x} A[i] = (x + 1) \sum_{i=1}^{x} D[i] \quad - \quad \sum_{i=1}^{x} (D[i] \times i)$$

마법 같은 구현 방법:

이 식을 계산하려면 두 개의 표준 펜윅 트리만 있으면 됩니다!

BIT1: $D[i]$의 누적 합을 유지합니다.
BIT2: $D[i] \times i$의 누적 합을 유지합니다.

구간 $[L, R]$에 값 $V$를 업데이트할 때마다 두 트리를 동시에 업데이트해 주면 됩니다.

RURQ 구현 코드 (Java)

두 개의 기본 펜윅 트리를 내부적으로 사용하는 깔끔하고 완벽한 구현체입니다.

public class FenwickTreeRURQ {
    private int n;
    private long[] bit1; // D[i]를 관리
    private long[] bit2; // D[i] * i를 관리

    public FenwickTreeRURQ(int size) {
        this.n = size;
        bit1 = new long[n + 1];
        bit2 = new long[n + 1];
    }

    // 표준 BIT 점 업데이트 헬퍼 메서드
    private void add(long[] bit, int i, long delta) {
        while (i <= n) {
            bit[i] += delta;
            i += (i & -i);
        }
    }

    // 구간 [L, R]에 V를 더함
    public void updateRange(int L, int R, long V) {
        // BIT1 업데이트 (차이 배열)
        add(bit1, L, V);
        add(bit1, R + 1, -V);

        // BIT2 업데이트 (차이 배열 * 인덱스)
        add(bit2, L, V * L);
        add(bit2, R + 1, -V * (R + 1));
    }

    // 표준 BIT 누적 합 쿼리 헬퍼 메서드
    private long query(long[] bit, int i) {
        long sum = 0;
        while (i > 0) {
            sum += bit[i];
            i -= (i & -i);
        }
        return sum;
    }

    // A[1]부터 A[x]까지의 누적 합 구하기
    public long prefixSum(int x) {
        // 수학 공식: (x + 1) * sum(D[i]) - sum(D[i] * i)
        long sum1 = query(bit1, x);
        long sum2 = query(bit2, x);
        return (x + 1) * sum1 - sum2;
    }

    // 구간 [L, R]의 합 구하기
    public long rangeSum(int L, int R) {
        return prefixSum(R) - prefixSum(L - 1);
    }
}

복잡도 분석

약간의 수학과 두 개의 트리를 사용함에도 불구하고, 성능은 여전히 믿을 수 없을 만큼 최적화되어 있습니다:

시간 (업데이트): $O(\log N)$ — 두 배열에 걸쳐 총 4번의 점 업데이트만 수행합니다.
시간 (쿼리): $O(\log N)$ — 두 배열에 걸쳐 총 4번의 점 쿼리만 수행합니다.
공간 복잡도: $O(N)$ — 크기가 $N+1$인 배열 두 개만 사용합니다.

초기화 최적화

기본 add() 메서드를 반복적으로 호출하여 펜윅 트리를 구축하면 $O(N \log N)$의 시간이 걸리지만, 이 방법을 사용하면 $O(N)$ (선형 시간) 만에 트리를 완전히 구성할 수 있습니다. 이는 거대한 배열을 초기화해야 하는 코딩 테스트나 고성능 백엔드 환경에서 특히 중요합니다.

1. 단순한 접근법: $O(N \log N)$

대부분의 사람들이 펜윅 트리 초기화에 대해 처음 배우는 표준적인 방법은 0으로 채워진 빈 배열에서 시작하여 입력 배열을 순회하며 각 요소에 대해 add() 함수를 호출하는 것입니다.

add() 함수 내부에는 트리를 타고 올라가며 $O(\log N)$ 단계가 걸리는 while 루프가 있기 때문에, $N$개의 요소에 대해 이 작업을 수행하면 총 $O(N \log N)$의 시간이 소요됩니다.

비유하자면, 매일의 영업 실적을 직속 상사에게만 보고하면 될 것을 굳이 매번 CEO의 사무실까지 걸어 올라가서 보고하는 것과 같습니다.

2. 핵심 아이디어: "직속 상사에게 떠넘기기"

이를 $O(N)$ 시간에 처리하기 위해 상향식(Bottom-up) 접근 방식을 사용합니다.

펜윅 트리의 구조를 생각해 보세요. 모든 노드 $i$는 트리 계층 구조에서 정확히 하나의 직속 부모(Immediate Parent) 에 속합니다. 부모의 구간은 자식의 구간을 완전히 포함합니다.

노드 $i$가 트리를 끝까지 타고 올라가며 모든 조상을 일일이 업데이트하는 대신, 노드 $i$는 자신의 값을 직속 부모에게 단 한 번만 더해주면 됩니다.

우리는 배열을 왼쪽에서 오른쪽($1$부터 $N$까지)으로 순차적으로 처리합니다. 따라서 루프가 어떤 부모 노드에 도달했을 때, 그 부모는 이미 자신보다 작은 모든 자식들로부터 합계를 안전하게 모두 수집해 둔 상태가 됩니다. 그러면 부모는 그렇게 모인 거대한 총합을 다시 자신의 부모에게 한 번에 넘겨주기만 하면 됩니다.

3. 수학적 원리 (직속 부모 찾기)

펜윅 트리에서 노드 $i$의 직속 부모(자신의 값을 필요로 하는 바로 위 노드)는 단순히 $i$에 자신의 최하위 비트(LSB)를 더한 값입니다.

$$parent = i + (i \ & \ -i)$$

4. 알고리즘 (단계별 설명)

배열 복사: 1-based 인덱스를 사용하는 tree 배열을 새로 만들고, 입력된 원본 값들을 그 자리에 그대로 복사해 넣습니다.
정방향 순회: $i$를 $1$부터 $N$까지 증가시키며 루프를 돕니다.
부모 찾기: $parent = i + (i & -i)$를 계산하여 직속 부모를 찾습니다.
값 전달(Propagate): 계산된 $parent$가 배열의 유효한 크기 내에 있다면($\le N$), tree[i]에 누적된 값을 tree[parent]에 더해줍니다.

5. 구현 코드 (Java)

고도로 최적화된 $O(N)$ 생성자 구현입니다.

public class FenwickTreeLinear {
    private int n;
    private long[] tree;

    // O(N) 초기화 생성자
    public FenwickTreeLinear(long[] values) {
        this.n = values.length;
        this.tree = new long[n + 1];

        // 1. 1-based 인덱스 트리에 원본 값들을 그대로 복사합니다.
        for (int i = 0; i < n; i++) {
            tree[i + 1] = values[i];
        }

        // 2. 누적된 값을 직속 부모에게 전달(Propagate)합니다.
        for (int i = 1; i <= n; i++) {
            int parent = i + (i & -i); // 직속 부모 계산
            
            // 부모가 트리의 범위 내에 있다면, 현재 노드의 총합을 부모에게 더해줍니다.
            if (parent <= n) {
                tree[parent] += tree[i];
            }
        }
    }

    // 표준 점 업데이트 (단일 요소 변경 시 사용)
    public void add(int i, long delta) {
        while (i <= n) {
            tree[i] += delta;
            i += (i & -i);
        }
    }

    // 표준 누적 합 쿼리
    public long query(int i) {
        long sum = 0;
        while (i > 0) {
            sum += tree[i];
            i -= (i & -i);
        }
        return sum;
    }
}

6. 복잡도 분석

지표	복잡도	설명
시간 복잡도	$O(N)$	배열을 정확히 두 번 순회합니다(복사할 때 한 번, 값을 전달할 때 한 번). 루프 내부에서는 $O(1)$의 덧셈과 비트 연산만 수행합니다.
공간 복잡도	$O(N)$	트리 배열을 위해 $N+1$ 크기의 메모리가 필요합니다.

이진 리프팅

이 개념을 이해하기 위해, 먼저 우리가 해결하려는 정확한 문제를 정의해 봅시다.

문제: 빈도수 배열 (Frequency Array) 펜윅 트리에 숫자 자체가 아니라 숫자의 빈도수(개수) 를 저장한다고 상상해 보세요.

숫자 5를 세 번 삽입한다면, add(5, 3)을 호출합니다.
이제 query(x)는 현재 수집된 숫자 중 $x$ 이하인 숫자가 몇 개인지를 알려줍니다.
목표: 이 컬렉션에서 $k$번째로 작은 숫자를 찾는 것입니다.

1. 왜 이진 탐색(Binary Search)을 쓰지 않을까요? ($O(\log^2 N)$)

$k$번째로 작은 원소를 찾는 가장 일반적인 방법은 이진 탐색과 펜윅 트리의 query() 함수를 결합하는 것입니다.

인덱스 mid를 추측합니다.
query(mid)를 호출하여 mid 이하의 요소가 몇 개인지 확인합니다.
합계가 $k$보다 작으면 정답은 더 커야 합니다. 합계가 $k$ 이상이면 정답은 mid이거나 더 작을 수 있습니다.
복잡도: 이진 탐색은 $O(\log N)$ 단계가 걸립니다. 각 단계 내부에서 query()가 $O(\log N)$ 시간을 소모합니다. 총 소요 시간은 $O(\log^2 N)$ 입니다.

우리는 이것보다 더 잘할 수 있습니다. 이진 리프팅(Binary Lifting) 을 사용하면 정확히 $O(\log N)$ 시간 만에 찾을 수 있습니다.

2. 핵심 개념: 이진 리프팅 (Binary Lifting)

이진 리프팅이란 최상위 비트(MSB, Most Significant Bit)부터 최하위 비트(LSB, Least Significant Bit)까지 내려가면서 정답을 비트 단위로 하나씩 조립해 나가는(Build) 것을 의미합니다.

펜윅 트리의 마법 같은 특성: 펜윅 트리의 구조를 기억하시나요? tree[idx] 노드는 자신의 LSB와 크기가 같은 특정 덩어리(Chunk)의 합을 저장합니다. 배열에서 2의 거듭제곱을 감소시키며(예: +16, +8, +4, +2, +1) 건너뛸 때, tree 배열은 그 점프에 필요한 정확한 덩어리의 합을 이미 가지고 있습니다! 즉, query() 함수를 다시 호출할 필요가 전혀 없습니다.

3. 알고리즘 (단계별 설명)

우리는 누적 합이 $k$보다 엄격하게 작은(strictly less than $k$) 가장 큰 인덱스를 찾고자 합니다. 이 인덱스를 pos라고 부릅시다. 이 값을 찾고 나면, $k$번째로 작은 요소는 단순히 pos + 1이 됩니다.

pos = 0과 current_sum = 0으로 초기화합니다.
트리의 최대 용량($N$)보다 작거나 같은 2의 거듭제곱 중 가장 큰 값을 찾습니다. 이를 step이라고 부릅시다.
step > 0인 동안 루프를 돕니다:
- next_pos = pos + step을 계산합니다.
- 검사: next_pos가 트리의 범위 내에 있고, 동시에 current_sum + tree[next_pos] < k인가요?
- 만약 YES라면: 이 전체 덩어리를 더하더라도 여전히 $k$번째 요소에 도달하지 못했다는 뜻입니다. 이 점프를 안전하게 "확정(Commit)"할 수 있습니다.
  - pos = next_pos
  - current_sum += tree[pos]
- 만약 NO라면: $k$번째 요소가 이 덩어리 안에 있거나, 배열 범위를 벗어났다는 뜻입니다. 점프를 뛰지 않고 그냥 넘어갑니다.
- 보폭을 반으로 줄입니다: step /= 2.
정답은 pos + 1입니다.

4. 트레이스 테이블 (시각화)

크기가 16인 펜윅 트리를 가정해 봅시다. 10번째로 작은 원소($k = 10$)를 찾으려고 합니다. 배열에 다음과 같은 빈도수가 있고, BIT가 이미 구축되어 있다고 가정해 보겠습니다:

인덱스	1	2	3	4	5	6	7	8	9	10	11	12
빈도수	2	0	1	3	1	2	0	1	2	4	0	1
누적 합	2	2	3	6	7	9	9	10	12	16	16	17

참고: 10번째 요소는 인덱스 8입니다 (누적 합이 인덱스 8에서 정확히 10에 도달하기 때문입니다).

이진 리프팅 알고리즘을 추적해 봅시다: MSB step = 8 (16 이하의 가장 큰 2의 거듭제곱은 16이므로 16부터 검사하지만 실패하고 8로 넘어왔다고 가정합니다). pos = 0, sum = 0.

Step (2의 거듭제곱)	다음 위치 (`pos + step`)	`tree[Next Pos]`의 값	검사: `sum + tree < 10`?	동작	새 `pos`	새 `sum`
8	$0 + 8 = 8$	`tree[8]`은 10	$0 + 10 < 10$ (거짓)	건너뜀	0	0
4	$0 + 4 = 4$	`tree[4]`는 6	$0 + 6 < 10$ (참)	점프!	4	6
2	$4 + 2 = 6$	`tree[6]`은 3	$6 + 3 < 10$ (참)	점프!	6	9
1	$6 + 1 = 7$	`tree[7]`은 0	$9 + 0 < 10$ (참)	점프!	7	9

루프가 종료됩니다. pos = 7. 정답 = pos + 1 = 8.

우리가 순식간에 4로, 그다음 6으로, 그리고 7로 점프한 것을 주목하세요. 우리는 정답 7의 이진수 표현(0111)을 단계별로 조립한 것입니다!

5. 구현 코드 (Java)

깔끔하게 최적화된 Java 구현체입니다.

public class FenwickTreeBinaryLifting {
    private int n;
    private int[] tree;
    private int msb;

    public FenwickTreeBinaryLifting(int size) {
        this.n = size;
        this.tree = new int[n + 1];
        
        // n보다 작거나 같은 2의 거듭제곱 중 가장 큰 값을 찾습니다.
        // Integer.highestOneBit()는 Java에서 제공하는 매우 빠른 비트 연산입니다.
        this.msb = Integer.highestOneBit(n); 
    }

    public void add(int i, int delta) {
        while (i <= n) {
            tree[i] += delta;
            i += (i & -i);
        }
    }

    // O(log N) 시간에 k번째로 작은 원소 찾기
    public int findKthSmallest(int k) {
        int pos = 0;
        int currentSum = 0;

        // MSB부터 1까지 2의 거듭제곱을 반씩 줄여가며 반복합니다.
        for (int step = msb; step > 0; step /= 2) {
            int nextPos = pos + step;

            // 배열 경계를 넘지 않으면서(<= n),
            // 누적 합이 k에 도달하지 않았는지(< k) 확인합니다.
            if (nextPos <= n && currentSum + tree[nextPos] < k) {
                pos = nextPos;
                currentSum += tree[nextPos];
            }
        }

        // pos는 sum < k를 만족하는 가장 큰 인덱스입니다.
        // 따라서 pos + 1은 sum >= k를 만족하는 첫 번째 인덱스(정답)가 됩니다.
        return pos + 1;
    }
}

6. 복잡도 분석

지표	복잡도	설명
시간 복잡도	$O(\log N)$	루프는 정확히 $\log N$번 실행됩니다(각 비트당 한 번). 루프 내부의 모든 연산은 $O(1)$입니다.
공간 복잡도	$O(N)$	표준 펜윅 트리의 배열 크기와 동일합니다.

references

1. 해결하려는 문제

2. 핵심 직관: 2의 거듭제곱

3. 마법의 공식: 최하위 비트 (LSB) 추출

4. 배열은 실제로 무엇을 저장하는가?

5. 두 가지 주요 연산

A. 쿼리 (인덱스 $i$까지의 누적 합)

B. 업데이트 (인덱스 $i$에 delta 더하기)

6. 구현 코드 (Java)

7. 복잡도 분석

요약 비교: 펜윅 트리 vs 세그먼트 트리

구간 업데이트

1단계: 구간 업데이트 + 점 쿼리 (RUPQ)

2단계: 구간 업데이트 + 구간 쿼리 (RURQ)

RURQ 구현 코드 (Java)

복잡도 분석

초기화 최적화

1. 단순한 접근법: $O(N \log N)$

2. 핵심 아이디어: "직속 상사에게 떠넘기기"

3. 수학적 원리 (직속 부모 찾기)

4. 알고리즘 (단계별 설명)

5. 구현 코드 (Java)

6. 복잡도 분석

이진 리프팅

1. 왜 이진 탐색(Binary Search)을 쓰지 않을까요? ($O(\log^2 N)$)

2. 핵심 개념: 이진 리프팅 (Binary Lifting)

3. 알고리즘 (단계별 설명)

4. 트레이스 테이블 (시각화)

5. 구현 코드 (Java)

6. 복잡도 분석

Related Posts

B. 업데이트 (인덱스 $i$에 `delta` 더하기)